package com.atwy.graph.mst;

import java.util.Arrays;

/**
 * @Author: 小王子火
 * @Date: 2022/3/16
 * 最小生成树--Prim算法
 * 最小生成树，图的一棵含有其所有顶点的无环连通子图。
 * 一幅加权图的最小生成树是它的一棵权值（树中所有边的权值之和）最小的生成树。
 * <p>
 * 回顾树的两个性质：对于n个顶点的连通图，只需n-1条边就能连通所有顶点。
 * 1、用一条边连接树中的任意两个顶点都会产生一个新的环；
 * 2、从树中删去一条边将会得到两棵独立的树。
 * <p>
 * <p>
 * 这两个性质是切分定理的基础。
 * <p>
 * 定义：图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。
 * 横切边：是一条连接两个属于不同集合的顶点的边。
 * <p>
 * 切分定理：在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。
 * 切分定理是解决最小生成树问题的所有算法的基础！
 * 更确切地说，这些算法都是一种贪心算法的特殊情况：
 * 使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。
 * <p>
 * 这些算法相互之间的不同之处在于保存切分和判定权重最小的横切边的方式。
 */
public class MST_Prim {
    /**
     * 7个村庄，A,B,C,D,E,F,G
     * A B 5
     * A C 7
     * A G 2
     * B G 3
     * B D 9
     * C E 8
     * D F 4
     * E F 5
     * E G 4
     * F G 6
     *
     * @param args
     */
    static int MAX = 10000;
    public static void main(String[] args) {

        int[][] map = {
                {MAX, 5, 7, MAX, MAX, MAX, 2},
                {5, MAX, MAX, 9, MAX, MAX, 3},
                {7, MAX, MAX, MAX, 8, MAX, MAX},
                {MAX, 9, MAX, MAX, MAX, 4, MAX},
                {MAX, MAX, 8, MAX, MAX, 5, 4},
                {MAX, MAX, MAX, 4, 5, MAX, 6},
                {2, 3, MAX, MAX, 4, 6, MAX}
        };

        int[] parent = new int[map.length];
        // 任选一个顶点为根节点
        int s = 0;
        //s=1;// 另选一个顶点也是正确的
        parent[s] = -1;
        int[] dist = new int[map.length];
        for (int i = 0; i < map[s].length; i++) {
            dist[i] = map[s][i];
            if (map[s][i] != MAX) {
                parent[i] = s;
            } else {
                parent[i] = -1;
            }
        }
        // dist[v]=0,表示在MST集合中
        dist[s] = 0;
        while (true) {
            //找到不在MST中的dist最小值的下标
            int v = findMin(dist);
            if (v == -1) {
                // 没找到，停止循环
                break;
            }
            // 将顶点v收录进MST集合
            dist[v] = 0;
            // 看下新收录顶点的不在MST中的邻接点对dist的影响
            // 有更小的边就更新dist和parent
            for (int w = 0; w < map[v].length; w++) {
                if (w != v && dist[w] != 0) {
                    if (map[v][w] < dist[w]) {
                        dist[w] = map[v][w];
                        parent[w] = v;
                    }
                }
            }
        }
        if (judgeMst(dist)) {
            System.out.println("生成树不存在");
            return;
        }

        System.out.println(Arrays.toString(parent));
        System.out.println("最小生成树所选边：");
        for (int i = 0; i < parent.length; i++) {
            if(parent[i]==-1){
                // 顶点跳过
                System.out.println("所选顶点是："+i);
                continue;
            }
            System.out.println("边："+parent[i]+"->"+i);
        }


    }

    private static boolean judgeMst(int[] dist) {
        for (int v : dist) {
            if (v != 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * dist[v]!=0表示不在MST集合中，找出不在MST中最小值的下标
     * 没找到返回-1
     *
     * @param dist
     * @return
     */
    private static int findMin(int[] dist) {
        int min = -1;
        int temp = MAX;
        // dist[v]!=0表示不在MST集合中，找出不在MST中最小值的下标
        for (int v = 0; v < dist.length; v++) {
            if (dist[v] != 0 && dist[v] < temp) {
                temp = dist[v];
                min = v;
            }
        }
        return min;
    }
    /**
     * 答案：
     * 所选顶点是：0
     * 边：6->1
     * 边：0->2
     * 边：5->3
     * 边：6->4
     * 边：4->5
     * 边：0->6
     */
}
